Shareware Grab Bag/Shareware Grab Bag.iso/050/madtrb10.arc/TREE.INC

Text File | 1985-12-05 | 52.5 KB | 1,285 lines

Procedure PrintHeading;

{ This procedure prints a heading for the program. }

Begin   { PrintHeading }
  WriteLn;
  WriteLn;
  WriteLn('MAIL ORDER PROCESSING DEMONSTRATION PROGRAM');
  WriteLn('-------------------------------------------');
  WriteLn;
End;    { PrintHeading }



Procedure InitPointers;

{ This procedure initializes the global pointers used in this program to Nil. }

Begin   { InitPointers }
  NewItemHeadPtr:=Nil;
  NewItemTailPtr:=Nil;
  AddQuantityHeadPtr:=Nil;
  AddQuantityTailPtr:=Nil;
  SellQuantityHeadPtr:=Nil;
  SellQuantityTailPtr:=Nil;
  RemoveItemHeadPtr:=Nil;
  RemoveItemTailPtr:=Nil;
  CurrentEmployeePtr:=Nil;
  TreeRootPtr:=Nil;
End;    { InitPointers }



Procedure RemoveFirstEntryFromString(Var Text:FileEntryString);

{ This procedure removes the first text entry from the passed text string and
  returns the new truncated text string.  The text entries in the passed text
  string are assumed to be delinated by one space.  See the following
  example.

         Passed:    Entry1  Entry2  Entry3
         Returned:  Entry2  Entry3                      }

Begin   { RemoveFirstEntryFromString }
  If Pos(' ',Text)<>0 Then
    Text:=Copy(Text,(Pos(' ',Text)+1),(Length(Text)-Pos(' ',Text)));
End;    { RemoveFirstEntryFromString }



Procedure ReturnFirstEntryFromString(Var Text:FileEntryString);

{ This procedure removes the first text entry from the passed text string and
  returns the first text entry.  The text entries in the passed text string
  are assumed to be delinated by one space.  See the following example.

         Passed:    Entry1  Entry2  Entry3
         Returned:  Entry1                              }

Begin   { ReturnFirstEntryFromString }
  If Pos(' ',Text)<>0 Then
    Text:=Copy(Text,1,(Pos(' ',Text)-1));
End;    { ReturnFirstEntryFromString }



Function TransactionCode(Entry:FileEntryString):EntryString;

{ This function is passed a file entry which contains a transaction code as the
  first entry.  This function picks off the transaction code from the file
  entry and passes the transaction code back. }

Begin   { TransactionCode }
  ReturnFirstEntryFromString(Entry);
  TransactionCode:=Entry;
End;    { TransactionCode }



Function ReturnSecondEntry(FileEntry:FileEntryString):EntryString;

{ This function is passed a file entry which contains entries seperated by a
  blank space.  This function picks off the second entry from the file entry
  and passes the second entry back. }

Begin   { ReturnSecondEntry }
  RemoveFirstEntryFromString(FileEntry);
  ReturnFirstEntryFromString(FileEntry);
  ReturnSecondEntry:=FileEntry;
End;    { ReturnSecondEntry }



Function ReturnThirdEntry(FileEntry:FileEntryString):EntryString;

{ This function is passed a file entry which contains entries seperated by a
  blank space.  This function picks off the third entry from the file entry and
  passes the third entry back. }

Begin   { ReturnThirdEntry }
  RemoveFirstEntryFromString(FileEntry);
  RemoveFirstEntryFromString(FileEntry);
  ReturnFirstEntryFromString(FileEntry);
  ReturnThirdEntry:=FileEntry;
End;    { ReturnThirdEntry }



Procedure PrintQueues;

{ This procedure is used to print out the contents of the four transaction
  queues. }

Var
  TempQueueElementPtr:QueueElementPtr; { a temporary pointer used in traversing the queues }

Begin   { PrintQueues }
  WriteLn;
  WriteLn;
  WriteLn('ITEMS LEFT ON TRANSACTION QUEUES :');
  WriteLn;
  WriteLn('     New Items Queue follows:');
  WriteLn;
  If NewItemHeadPtr=Nil Then
      WriteLn('          No items on queue.')
  Else
    Begin
      TempQueueElementPtr:=NewItemHeadPtr;
      While TempQueueElementPtr<>Nil Do
        Begin
          WriteLn('          Item Name : ',TempQueueElementPtr^.ItemName,
                  '   Quantity : ',TempQueueElementPtr^.ItemQuantity);
          TempQueueElementPtr:=TempQueueElementPtr^.Back; { increment queue pointer }
        End; { While TempQueueElementPtr }
    End; { Else }
  WriteLn;
  WriteLn;
  WriteLn('     Added Quantity Items Queue follows:');
  WriteLn;
  If AddQuantityHeadPtr=Nil Then
      WriteLn('          No items on queue.')
  Else
    Begin
      TempQueueElementPtr:=AddQuantityHeadPtr;
      While TempQueueElementPtr<>Nil Do
        Begin
          WriteLn('          Item Name : ',TempQueueElementPtr^.ItemName,
                  '   Quantity : ',TempQueueElementPtr^.ItemQuantity);
          TempQueueElementPtr:=TempQueueElementPtr^.Back; { increment queue pointer }
        End; { While TempQueueElementPtr }
    End; { Else }
  WriteLn;
  WriteLn;
  WriteLn('     Sell Items Queue follows:');
  WriteLn;
  If SellQuantityHeadPtr=Nil Then
      WriteLn('          No items on queue.')
  Else
    Begin
      TempQueueElementPtr:=SellQuantityHeadPtr;
      While TempQueueElementPtr<>Nil Do
        Begin
          WriteLn('          Item Name : ',TempQueueElementPtr^.ItemName,
                  '   Quantity : ',TempQueueElementPtr^.ItemQuantity);
          TempQueueElementPtr:=TempQueueElementPtr^.Back; { increment queue pointer }
        End; { While TempQueueElementPtr }
    End; { Else }
  WriteLn;
  WriteLn;
  WriteLn('     Remove Items Queue follows:');
  WriteLn;
  If RemoveItemHeadPtr=Nil Then
      WriteLn('          No items on queue.')
  Else
    Begin
      TempQueueElementPtr:=RemoveItemHeadPtr;
      While TempQueueElementPtr<>Nil Do
        Begin
          WriteLn('          Item Name : ',TempQueueElementPtr^.ItemName);
          TempQueueElementPtr:=TempQueueElementPtr^.Back; { increment queue pointer }
        End; { While TempQueueElementPtr }
    End; { Else }
  WriteLn;
  WriteLn('END OF DAY');
  WriteLn('----------');
  WriteLn;
  WriteLn;
End;    { PrintQueues }



Procedure PrintEmployeeQueue;

{ This procedure is used to print out the contents of the doubly linked
  circular employee queue. }

Var
  TempQueueElementPtr:EmployeePtr;     { a temporary pointer used in traversing the queue }

Begin   { PrintEmployeeQueue }
  WriteLn;
  WriteLn;
  WriteLn('LIST OF CURRENT MAIL ORDER CLERKS :');
  WriteLn;
  If CurrentEmployeePtr=Nil Then
    WriteLn('     No Employees In Employee Queue')
  Else
    Begin
      TempQueueElementPtr:=CurrentEmployeePtr;
      Repeat;
        WriteLn('     ',TempQueueElementPtr^.EmployeeName);
        TempQueueElementPtr:=TempQueueElementPtr^.NextEmployee;
      Until TempQueueElementPtr=CurrentEmployeePtr;
    End; { Else }
End;    { PrintEmployeeQueue }



Procedure AddElementToQueue(Var HeadPtr,TailPtr:QueueElementPtr;FileEntry:FileEntryString);

{ This procedure adds a queue element to the end of the passed tail pointer
  of a particular doubly linked transaction queue.   There are four transaction
  queues which correspond to:

              Insert a new item into the store's inventory.
              Add a quantity to an existing item.
              Sell a quantity of an existing item.
              Remove an item from the store's inventory.

  By adding the queue element to the end of the passed tail pointer, this
  maintains first in/first out (FIFO) order.

  Note that there are two special cases when inserting a queue element into a
  particular transaction queue:

              1. Empty transaction queue.
              2. Transaction queue present.          }

Var
  NewQueueElement:QueueElementPtr; { a pointer to a new queue element which will be added to the tail
                                         of the passed transaction queue }

Begin   { AddElementToQueue }
  New(NewQueueElement);                { create a new queue element to add to the end of the passed queue }
  With NewQueueElement^ Do
    Begin                              { routine to enter information into the new queue element }
      ItemName:=ReturnSecondEntry(FileEntry);
      ItemQuantity:=ReturnThirdEntry(FileEntry);
      Front:=Nil;                      { set forward pointer to Nil }
      Back:=Nil;                       { set backward pointer to Nil }
    End; { With NewQueueElement }
  { Special Case One - Check for existance of transaction queue }
  If HeadPtr=Nil Then
    Begin
      HeadPtr:=NewQueueElement;        { set particular queue head pointer to point to the first element in the queue }
      TailPtr:=NewQueueElement;        { set particular queue tail pointer to point to the first element in the queue }
    End { If HeadPtr }
  Else
    { Special Case Two - existant transaction queue }
    Begin
      TailPtr^.Back:=NewQueueElement;  { link new queue element to end of the transaction queue }
      NewQueueElement^.Front:=TailPtr; { link new queue element to end of the transaction queue }
      TailPtr:=NewQueueElement;        { increment tail pointer }
    End; { Else }
End;    { AddElementToQueue }



Procedure ProcessEmployeeModule(FileEntry:FileEntryString);

{ This module controls the hiring and quiting of mail order clerks.

  To facilitate insertions and deletions of mail order clerks into the
  employee pool, a doubly linked circular queue is used.

  If a new clerk is added to the queue with the HIRE command, he/she is added
  to the spot behind the current employee, i.e. added to the end of the
  current cycle to have time to learn the system.

  When clerks quit their job, they are removed from the circular queue.  If the
  current employee happens to be the clerk that quit, the current employee is
  then moved forward to the next clerk in the queue.  The current employee is
  the current mail order clerk that is processing transactions. }

Var
  Command:EntryString;                 { a string used to store the employee processing command }
  Name:EntryString;                    { a string used to store the employee name }



  Function EmployeeExist(Name:ClerkString):Boolean;

  { This function determines if the passed name is a name of an employee that
    already works for the store.  If the passed name exists then this function
    returns as true, else it returns as false. }

  Var
    TempEmployeePtr:EmployeePtr;       { a temporary pointer used in searching for an employee already
                                         existant in the employee queue }
    Found:Boolean;                     { a flag used in detecting if the employee was successfully deleted
                                         from the queue }

  Begin   { EmployeeExist }
    Found:=False;
    TempEmployeePtr:=CurrentEmployeePtr;
    If TempEmployeePtr<>Nil Then
      Repeat { search routine }
        If TempEmployeePtr^.EmployeeName=Name Then
          Found:=True
        Else
          TempEmployeePtr:=TempEmployeePtr^.NextEmployee;
      Until (TempEmployeePtr=CurrentEmployeePtr) Or Found;
    EmployeeExist:=Found; { pass back result of search }
  End;    { EmployeeExist }



  Procedure HireEmployee(Name:ClerkString);

  { This procedure inserts the newly hired employee into the employee pool,
    which is represented by a doubly linked circular list.

    There are two special cases when trying to insert an employee into the
    doubly linked circular queue:

           1. If no employees are yet present in the queue, the newly hired
              employee becomes the current employee.

           2. The newly hired employee already exists in the employee queue.
              Ignore this hire command.

           3. Otherwise, the new clerk is added to the queue at the spot behind
              the current employee, i.e. added to the end of the current cycle
              to have time to learn the system. }

  Var
    NewEmployee:EmployeePtr;           { a pointer to the newly hired employee }

  Begin   { HireEmployee }
    If Not EmployeeExist(Name) Then
      Begin { new employee }
        New(NewEmployee);                  { create a new employee queue element to add to the queue }
        With NewEmployee^ Do
          Begin
            EmployeeName:=Name;
            ItemsProcessedDuringShift:=0;
            If CurrentEmployeePtr=Nil Then
              Begin
                { No employees yet present in the queue }
                NextEmployee:=NewEmployee; { next employee in the queue is itself }
                LastEmployee:=NewEmployee; { last employee in the queue is itself }
                CurrentEmployeePtr:=NewEmployee; { newly hired employee becomes the current employee }
              End { If CurrentEmployeePtr }
            Else
              Begin
                { Queue is present, link new employee into queue just behind current employee }
                NextEmployee:=CurrentEmployeePtr;
                LastEmployee:=CurrentEmployeePtr^.LastEmployee;
                CurrentEmployeePtr^.LastEmployee^.NextEmployee:=NewEmployee; { relink queue }
                CurrentEmployeePtr^.LastEmployee:=NewEmployee; { relink queue }
              End; { Else }
            WriteLn;
            WriteLn('The newly hired employee ',EmployeeName,' was inserted into the employee queue.');
          End; { With NewEmployee }
      End { If Not EmployeeExist }
    Else { new employee already exists in the employee pool }
      Begin
        WriteLn;
        WriteLn('The already existant employee ',Name,' somehow was placed');
        WriteLn('in the transaction file as a new emploee that was hired.  The');
        WriteLn('false transaction has been ignored.');
      End; { Else }
  End;    { HireEmployee }



  Procedure EmployeeQuit(Var Name:ClerkString);

  { This procedure deletes the employee from the employee pool who has just
    quit.

    There are four special cases when trying to delete an employee from the
    doubly linked circular queue:

           1. If the clerk that quit was the last element in the queue, then
              the current employee pointer is then set to nil.

           2. If the current employee happens to be the clerk that quit, the
              current employee is then moved forward to the next clerk in the
              queue.

           3. If the clerk that quit is not the current employee then the queue
              is traversed until the proper element is found and deleted.

           4. The clerk that quit was never in the queue. }

  Var
    Found:Boolean;                     { a flag used in detecting if the employee was successfully deleted
                                         from the queue }
    TempEmployeePtr:EmployeePtr;       { a temporary pointer used in deleting a employee
                                         from the queue }

  Begin   { EmployeeQuit }
    Found:=False;                      { initialize flag }
    If CurrentEmployeePtr<>Nil Then
      Begin
        { Special Case One - Check if clerk is last element in queue }
        If (Name=CurrentEmployeePtr^.EmployeeName) And (CurrentEmployeePtr^.NextEmployee=CurrentEmployeePtr) Then
          Begin { Delete last remaining employee from queue }
            Dispose(CurrentEmployeePtr);
            CurrentEmployeePtr:=Nil;
            Found:=True; { set flag }
          End { If Name }
        Else
          { Special Case Two - Check if clerk is current employee }
          If Name=CurrentEmployeePtr^.EmployeeName Then
            Begin { delete current employee from queue }
              TempEmployeePtr:=CurrentEmployeePtr; { temporarily store employee for deleting later }
              CurrentEmployeePtr^.NextEmployee^.LastEmployee:=CurrentEmployeePtr^.LastEmployee; { relink queue }
              CurrentEmployeePtr^.LastEmployee^.NextEmployee:=CurrentEmployeePtr^.NextEmployee; { relink queue }
              CurrentEmployeePtr:=CurrentEmployeePtr^.NextEmployee; { increment  current employee pointer to point
                                                                      to next employee in the queue }
              Dispose(TempEmployeePtr);
              Found:=True; { set flag }
            End { If Name }
          Else
            { Special Case Three - Try to find clerk to delete in the circular queue }
            Begin
              TempEmployeePtr:=CurrentEmployeePtr^.NextEmployee;
              While (TempEmployeePtr<>CurrentEmployeePtr) And Not Found Do
                Begin
                  If TempEmployeePtr^.EmployeeName=Name Then
                    Begin { delete employee from queue }
                      TempEmployeePtr^.NextEmployee^.LastEmployee:=TempEmployeePtr^.LastEmployee; { relink queue }
                      TempEmployeePtr^.LastEmployee^.NextEmployee:=TempEmployeePtr^.NextEmployee; { relink queue }
                      Dispose(TempEmployeePtr);
                      Found:=True; { set flag }
                    End { If TempEmployeePtr }
                  Else
                    TempEmployeePtr:=TempEmployeePtr^.NextEmployee; { incrementQueue pointer }
                End; { While TempEmployeePtr }
            End; { Else }
      End; { If CurrentEmployeePtr }
    WriteLn;
    If Not Found Then
      Begin
        WriteLn('The employee ',Name,' has quit but could not be deleted from the');
        WriteLn('queue because the name could not be found to exist in the employee queue.');
      End { If Not Found }
    Else
      WriteLn('The employee ',Name,' has quit and was deleted from the employee queue.');
  End;    { EmployeeQuit }



Begin   { ProcessEmployeeModule }
  Command:=ReturnSecondEntry(FileEntry); { determine employee processing command }
  Name:=ReturnThirdEntry(FileEntry);     { determine employee's name }
  If Command='HIRE' Then
    HireEmployee(Name)                   { pass control to specific employee processing procedure }
  Else
    EmployeeQuit(Name);                  { pass control to specific employee processing procedure }
End;    { ProcessEmployeeModule }



Procedure DeleteElementFromTreeModule(Item:ItemString);

{ This module controls the deletion of an element corresponding to the above
  passed item from the binary search tree.

  Note that there are three special cases when deleting an element from a
  binary search tree:

           1. Delete an element with no children.
           2. Delete an element with one child.
           3. Delete an element with two children.

  This procedure begins by searching for the node that contains the element to
  be deleted from the tree.  If that node has an empty subtree, then that node
  is removed from the tree.  If not, then the content of that node is replaced
  by its predecessor, (or the right most node in its left subtree).  The
  predecessor will always have an empty right subtree.

  A special circumstance occurs when the root element is the element to be
  deleted.

  Note also that the calling routine must check to see that the passed item
  actually exists in the tree. }

Var
  DeletedElementNodePtr:TreeNodePtr;   { a pointer used to point to the deleted element in the binary search tree }
  DeletedElementParentPtr:TreeNodePtr; { a pointer used to point to the deleted element's parent }



  Procedure FindElementToDelete(Var TreeNode,TreeNodeParent:TreeNodePtr);

  { This recursive procedure is used to find the element which is to be deleted
    from the tree.  Refernce is saved to the deleted element's parent. }

  Begin   { FindElementToDelete }
    { Recursive search for element to be deleted }
    If Item<TreeNode^.ItemName Then
      FindElementToDelete(TreeNode^.Left,TreeNode)
    Else { If Item }
      If Item>TreeNode^.ItemName Then
        FindElementToDelete(TreeNode^.Right,TreeNode)
      Else { end of recursive search }
        Begin { found element to be deleted from tree }
          DeletedElementNodePtr:=TreeNode; {save reference to deleted element's node }
          DeletedElementParentPtr:=TreeNodeParent; { save reference to deleted element's parent }
        End; { Else }
  End;    { FindElementToDelete }



  Procedure PlacePredecessorIntoEmptyNode(TreeNode,TreeNodeParent:TreeNodePtr);

  { This recursive procedure is used to determine the immeadiate predecessor to
    the deleted element (which now is an empty tree node) and place the
    predecessor's contents into the deleted element's empty tree node.  It then
    links the predecessor's left child to its parent's right branch.  Note that
    the predecessor's right child must be nil by definition. }

  Begin   { PlacePredecessorIntoEmptyNode }
    { recursive search for the right most element in the left subtree }
    If TreeNode^.Right<>Nil Then
      PlacePredecessorIntoEmptyNode(TreeNode^.Right,TreeNode)
    Else
      Begin { found right most element in the left subtree }
        { transfer element contents from predecessor to empty node }
        DeletedElementNodePtr^.ItemName:=TreeNode^.ItemName;
        DeletedElementNodePtr^.ItemQuantity:=TreeNode^.ItemQuantity;
        { dispose of predecessor node and relink its left child to it's parent's right branch }
        TreeNodeParent^.Right:=TreeNode^.Left;
        Dispose(TreeNode);
      End; { Else }
  End;    { PlacePredecessorIntoEmptyNode }



Begin   { DeleteElementFromTreeModule }
  FindElementToDelete(TreeRootPtr,TreeRootPtr);
  If DeletedElementNodePtr=TreeRootPtr Then { special concern since no parent to the root }
    With DeletedElementNodePtr^ Do
      Begin
        If (Left=Nil) And (Right=Nil) Then
          Begin { Special Case One }
            Dispose(DeletedElementNodePtr); { remove root }
            TreeRootPtr:=Nil;          { reset tree root pointer to Nil }
          End { Secial Case One }
        Else
          If Left=Nil Then
            Begin { Special Case Two }
              TreeRootPtr:=Right;      { increment tree root pointer }
              Dispose(DeletedElementNodePtr);
            End { Special Case Two }
          Else
            If Right=Nil Then
              Begin { Special Case Two }
                TreeRootPtr:=Left;     { increment tree root pointer }
                Dispose(DeletedElementNodePtr);
              End { Special Case Two }
            Else { Special Case Three }
              PlacePredecessorIntoEmptyNode(DeletedElementNodePtr,DeletedElementParentPtr);
      End { With DeletedElementNodePtr^ }
  Else { deleted element is not tree root }
    With DeletedElementNodePtr^ Do
      Begin
        If (Left=Nil) And (Right=Nil) Then
          Begin { Special Case One }
            { routine to determine which parent field to set to Nil }
            If DeletedElementParentPtr^.Left=DeletedElementNodePtr Then
              DeletedElementParentPtr^.Left:=Nil
            Else
              DeletedElementParentPtr^.Right:=Nil;
            Dispose(DeletedElementNodePtr);
          End { Special Case One }
        Else
          If Left=Nil Then
            Begin { Special Case Two }
              { routine to determine which parent field to relink }
              If DeletedElementParentPtr^.Left=DeletedElementNodePtr Then
                DeletedElementParentPtr^.Left:=Right
              Else
                DeletedElementParentPtr^.Right:=Right;
              Dispose(DeletedElementNodePtr);
            End { Special Case Two }
          Else
            If Right=Nil Then
              Begin { Special Case Two }
                { routine to determine which parent field to relink }
                If DeletedElementParentPtr^.Left=DeletedElementNodePtr Then
                  DeletedElementParentPtr^.Left:=Left
                Else
                  DeletedElementParentPtr^.Right:=Left;
                Dispose(DeletedElementNodePtr);
              End { Special Case Two }
            Else { Special Case Three }
              PlacePredecessorIntoEmptyNode(DeletedElementNodePtr,DeletedElementParentPtr);
      End; { With DeletedElementNodePtr^ }
End;    { DeleteElementFromTreeModule }



Procedure ProcessDailyOrdersModule;

{ This module controls the processing of all the transactions that have occured
  in the previous 24 hours.  The transactions have previously been placed in a
  particular transaction queue for processing.  The four queues are processed
  in the following order:

              1. Insert a new item into the store's inventory
              2. Add a quantity to an existing item
              3. Sell a quantity of an existing item
              4. Remove an item from the store's inventory

  Control is passed to a particular procedure within this module inorder to
  process the transaction queues. }



  Procedure PrintTransactionsHandledHeading;

  { This procedure prints out the transactions handled heading for the daily
    worklog report. }

  Begin   { PrintTransactionsHandledHeading }
    WriteLn;
    WriteLn;
    WriteLn('TRANSACTIONS PROCESSED :');
  End;    { PrintTransactionsHandledHeading }



  Procedure RemoveElementFromQueue(Var HeadPtr,TailPtr,CurrentQueueElement,RemovedQueueElement:QueueElementPtr);

  { This procedure removes the queue element from within the passed doubly
    linked transaction queue.  There are four transaction queues which
    correspond to:

                Insert a new item into the store's inventory.
                Add a quantity to an existing item.
                Sell a quantity of an existing item.
                Remove an item from the store's inventory.

    Note that this procedure does not simply remove queue elements from the
    front of the passed queue, but will remove queue elements from anywhere
    the current queue pointer happens to be pointing to.  This is necessary,
    for example, when a particular transaction cannot be met and it is
    necessary to keep that transaction on the queue for the next business
    day.

    Example queue:
                                   __CurrentQueueElement
                                  |  (after being incremented)
                        ______    v
            __     __  |  __  |  __     __     __     __
           |__|-->|__|-- |__| ->|__|-->|__|-->|__|-->|__|-->Nil

    HeadPtr--^             ^--RemovedQueueElement      ^--TailPtr
                              (previous
                               CurrentQueueElement)

    Note that there are four special cases when deleting a queue element from
    a particular transaction queue:

                1. Delete last remaining queue element from queue.
                2. Delete queue element from front of the queue.
                3. Delete queue element from end of queue.
                4. Delete queue element from middle of queue.    }

  Begin   { RemoveElementFromQueue }
    { Special Case One - Check if delete last remaining queue element from queue }
    If HeadPtr=TailPtr Then
      Begin { delete last remaining queue element from queue }
        HeadPtr:=Nil;
        TailPtr:=Nil;
      End { If HeadPtr }
    Else
      { Special Case Two - Check if delete queue element from front of queue }
      If HeadPtr=CurrentQueueElement Then
        Begin { delete queue element from front of queue }
          CurrentQueueElement^.Back^.Front:=Nil; { release link with queue }
          HeadPtr:=CurrentQueueElement^.Back;    { increment head pointer }
        End { If HeadPtr }
      Else
        { Special Case Three - Check if delete queue element from rear of queue }
        If TailPtr=CurrentQueueElement Then
          Begin { delete queue element from end of queue }
            CurrentQueueElement^.Front^.Back:=Nil; { release link with queue }
            TailPtr:=CurrentQueueElement^.Front;   { de-increment tail pointer }
          End { If TailPtr }
        Else
          { Special Case Four - Delete queue element from middle of queue }
            Begin
              CurrentQueueElement^.Front^.Back:=CurrentQueueElement^.Back;  { relink queue }
              CurrentQueueElement^.Back^.Front:=CurrentQueueElement^.Front; { relink queue }
            End; { Else }
    RemovedQueueElement:=CurrentQueueElement;
    CurrentQueueElement:=CurrentQueueElement^.Back; { increment current queue element pointer }
  End;    { RemoveElementFromQueue }



  Procedure DetermineMailOrderClerk(Var Name:ClerkString);

  { This procedure returns the mail order clerk name which is processing the
    current transaction.

    Each clerk processes just two transactions during his shift even if one of
    the transactions caused an error.  Also, if a clerk only finishes one
    transaction at the end of the day at the start of the next day the clerk
    finishes the second transaction, unless he quits in between.

    If the current clerk has only processed one transaction, the
    ItemsProcessedDuringShift counter is incremented one.  If the current clerk
    Has processed two transactions the the CurrentEmployeePtr is incremented
    in the queue and the counter in the previous employee is reset. }

  Begin   { DetermineMailOrderClerk }
    With CurrentEmployeePtr^ Do
      Begin
        Name:=EmployeeName; { return name of processing clerk to calling routine }
        { routine to increment current employee pointer }
        If ItemsProcessedDuringShift=0 Then
          ItemsProcessedDuringShift:=ItemsProcessedDuringShift+1 { increment couter }
        Else
          Begin { increment current employee pointer }
            ItemsProcessedDuringShift:=0; { reset counter }
            CurrentEmployeePtr:=NextEmployee; { increment current employee pointer }
          End; { Else }
      End; { With CurrentEmployeePtr }
  End;    { DetermineMailOrderClerk }



  Function EmptyQueue(QueueHeadPtr:QueueElementPtr):Boolean;

  { This function is used to check if the passed queue is empty.  If the queue
    is empty this function returns as true, else it returns as false. }

  Begin   { EmptyQueue }
    If QueueHeadPtr=Nil Then
      EmptyQueue:=True
    Else
      EmptyQueue:=False;
  End;    { EmptyQueue }



  Function TreeNode(Item:ItemString):TreeNodePtr;

  { This function is used to find the passed item in the binary search tree and
    returns a tree node pointer pointing to the found item.  If the item does
    not exist in the binary tree then this function returns as nil. }

  Var
    TempTreeNodePtr:TreeNodePtr;       { a temporary tree node pointer used in traversing a the binary search tree }
    Found:Boolean;                     { a flag used to determine if the passed item exists in the binary search tree }

  Begin   { TreeNode }
    Found:=False;                      { initialize flag }
    TempTreeNodePtr:=TreeRootPtr;      { start at the root of the binary search tree }
    While (TempTreeNodePtr<>Nil) And Not Found Do
      With TempTreeNodePtr^ DO
        Begin
          If Item=ItemName Then
            Found:=True                { item is in binary search tree }
          Else
            If Item<ItemName Then
              TempTreeNodePtr:=Left    { follow down left branch of subtree }
            Else
              TempTreeNodePtr:=Right;  { follow down right branch of subtree }
        End; { With TempTreeNodePtr^ }
    If Found Then
      TreeNode:=TempTreeNodePtr        { return a pointer to the found item in the binary search tree }
    Else
      TreeNode:=Nil;                   { item not in binary search tree, return to calling routine as nil }
  End;    { TreeNode }



  Function ItemExist(Item:ItemString):Boolean;

  { This function determines if the passed item exists in the binary search
    tree.  If the passed item exists this function returns as true, else it
    returns as false. }

  Begin   { ItemExist }
    If TreeNode(Item)<>Nil Then
      ItemExist:=True
    Else
      ItemExist:=False;
  End;    { ItemExist }



  Function QuantityOfItem(Item:ItemString):Integer;

  { This function returns to the calling routine the quantity of the above
    passed item that is stored in the binary search tree. }

  Var
    TempTreeNodePtr:TreeNodePtr;       { a temporary tree node pointer which points to a node in the binary search tree }

  Begin   { QuantityOfItem }
    TempTreeNodePtr:=TreeNode(Item);   { get a pointer to the passed item in the binary search tree }
    QuantityOfItem:=TempTreeNodePtr^.ItemQuantity; { return quantity of item to calling routine }
  End;    { QuantityOfItem }



  Procedure ReviseQuantityInTreeNode(Item:ItemString;Quantity:Integer);

  { This procedure is used to revise the quantity of the above passed item that
    which are stored in the binary search tree.  The above passed quantity is
    added to the quantity stored under the particular tree node.  A passed
    positve quantity corresponds to receiving a shipment of stock of the above
    passed item.  A passed negative quantity corresponds to selling some stock
    of the above passed item. }

  Var
    TempTreeNodePtr:TreeNodePtr;       { a temporary tree node pointer which points to a node in the binary search tree }

  Begin   { ReviseQuantityInTreeNode }
    TempTreeNodePtr:=TreeNode(Item);   { get a pointer to the passed item in the binary search tree }
    TempTreeNodePtr^.ItemQuantity:=TempTreeNodePtr^.ItemQuantity+Quantity; { revise quantity stored in binary search tree }
  End;    { ReviseQuantityInTreeNode }



  Procedure AddNodeToTree(Item:ItemString;Quantity:Integer);

  { This procedure is used to add the above passed quantity of the above passed
    new item (node) into the binary search tree.  It should be noted that new
    nodes are always inserted into a binary search tree as leaf nodes.  Note
    also that this procedure does not check to see if the above passed item
    already exists in the binary search tree.  The calling routine should first
    check to see that the passed item does not already exist by using the above
    function ItemExist.

    Example binary search tree:

                               O  <----TreeRootPtr
                              / \
                            /     \
        a Nil node---->   Nil       O   <----a tree node
                                   /  \
                                 /      \
                               Nil       O  <----NewNode (just inserted)
                                        /  \
                                      /      \
                                    Nil      Nil  }

  Type
    DirectionType=(LeftBranch,RightBranch); { an enumerated data type used in helping to determine tree traversing
                                              direction }

  Var
    TempTreeNodePtr:TreeNodePtr;       { a temporary tree node pointer used in traversing a the binary search tree }
    TempParentNodePtr:TreeNodePtr;     { a temporary tree node pointer used in pointing to the previous tree node
                                         while traversing the binary search tree }
    Direction:DirectionType;           { a temporary index used in connecting a new tree node to an existant tree node }
    NewNode:TreeNodePtr;               { a pointer to the new tree node }

  Begin   { AddNodeToTree }
    TempTreeNodePtr:=TreeRootPtr;      { start at the root of the binary search tree }
    While TempTreeNodePtr<>Nil Do      { search routine to find proper location in tree for new node }
      With TempTreeNodePtr^ DO
        Begin
          If Item<ItemName Then
            Begin { traverse down left subtree }
              TempParentNodePtr:=TempTreeNodePtr; { save reference to previous tree node }
              TempTreeNodePtr:=Left;   { follow down left branch of subtree }
              Direction:=LeftBranch;
            End { If Item }
          Else
            Begin { traverse down right subtree }
              TempParentNodePtr:=TempTreeNodePtr; { save reference to previous tree node }
              TempTreeNodePtr:=Right;  { follow down right branch of subtree }
              Direction:=RightBranch;
            End; { Else }
        End; { With TempTreeNodePtr^ }
    New(NewNode);                      { create a new tree node to insert into the binary search tree }
    With NewNode^ Do
      Begin { initialize routine }
        ItemName:=Item;
        ItemQuantity:=Quantity;
        Left:=Nil;
        Right:=Nil;
      End; { With NewNode^ }
    If TreeRootPtr=Nil Then
      TreeRootPtr:=NewNode
    Else { routine to link new node to parent node }
      If Direction=LeftBranch Then
        TempParentNodePtr^.Left:=NewNode
      Else
        TempParentNodePtr^.Right:=NewNode;
  End;    { AddNodeToTree }



  Procedure AddItemsToInventory;

  { This procedure processes the AddItemToInventory queue.  This queue contains
    transactions to add new items to the store's inventory.

    This procedure first assigns a mail order clerk to process the transaction.
    It then checks if the new item already exists in the store's inventory.  If
    it does then the appropriate error message is printed.  Otherwise the new
    item is added to the store's inventory with the appropriate message printed. }

  Var
    ClerkName:EntryString;               { name of the processing clerk }
    CurrentQueueElement:QueueElementPtr; { a pointer the current queue element being processed in the queue }
    RemovedQueueElement:QueueElementPtr; { a temporary pointer to the removed queue element }
    Quantity:Integer;                    { the number of items to be added to the store's inventory }
    ErrorCode:Integer;                   { an error code returned by the function Val }

  Begin   { AddItemsToInventory }
    CurrentQueueElement:=NewItemHeadPtr;
    While Not EmptyQueue(CurrentQueueElement) Do
      Begin
        DetermineMailOrderClerk(ClerkName);
        RemoveElementFromQueue(NewItemHeadPtr,NewItemTailPtr,CurrentQueueElement,RemovedQueueElement);
        If ItemExist(RemovedQueueElement^.ItemName) Then
          Begin { new item already exists in store's inventory }
            Val(RemovedQueueElement^.ItemQuantity,Quantity,ErrorCode); { convert string quantity to an integer quantity }
            ReviseQuantityInTreeNode(RemovedQueueElement^.ItemName,Quantity);
            WriteLn;
            WriteLn(ClerkName,' has found that ',RemovedQueueElement^.ItemName,' already exists in the');
            WriteLn('store`s inventory but has added the ',RemovedQueueElement^.ItemQuantity,' of the item ',
                     RemovedQueueElement^.ItemName);
            WriteLn('to the store`s inventory.');
          End { If ItemExist }
        Else
          Begin { add new item to store's inventory }
            Val(RemovedQueueElement^.ItemQuantity,Quantity,ErrorCode); { convert string quantity to an integer quantity }
            AddNodeToTree(RemovedQueueElement^.ItemName,Quantity);
            WriteLn;
            WriteLn(ClerkName,' has added ',RemovedQueueElement^.ItemQuantity,' of the new item ',
                    RemovedQueueElement^.ItemName,' to the');
            WriteLn('store`s inventory.');
          End; { Else }
        Dispose(RemovedQueueElement);
      End; { While Not EmptyQueue }
  End;    { AddItemsToInventory }



  Procedure AddStockToItems;

  { This procedure processes the AddQuantityToItem queue.  This queue contains
    transactions to add quantity of an item to the store's inventory.

    This procedure first assigns a mail order clerk to process the transaction.
    It then checks if the new item exists in the store's inventory.  If not
    then the appropriate error message is printed.  Otherwise the additional
    stock is added to the store's inventory with the appropriate message
    printed. }

  Var
    ClerkName:EntryString;               { name of the processing clerk }
    CurrentQueueElement:QueueElementPtr; { a pointer the current queue element being processed in the queue }
    RemovedQueueElement:QueueElementPtr; { a temporary pointer to the removed queue element }
    Quantity:Integer;                    { the number of items to be added to the store's inventory }
    ErrorCode:Integer;                   { an error code returned by the function Val }

  Begin   { AddStockToItems }
    CurrentQueueElement:=AddQuantityHeadPtr;
    While Not EmptyQueue(CurrentQueueElement) Do
      Begin
        DetermineMailOrderClerk(ClerkName);
        RemoveElementFromQueue(AddQuantityHeadPtr,AddQuantityTailPtr,CurrentQueueElement,RemovedQueueElement);
        If Not ItemExist(RemovedQueueElement^.ItemName) Then
          Begin { item does not exist in store's inventory }
            WriteLn;
            WriteLn(ClerkName,' has found that ',RemovedQueueElement^.ItemName,' does not exist in the');
            WriteLn('store`s inventory and therefore could not add to previous stock.');
          End { If Not ItemExist }
        Else
          Begin { add stock to store's inventory }
            Val(RemovedQueueElement^.ItemQuantity,Quantity,ErrorCode); { convert string quantity to an integer quantity }
            ReviseQuantityInTreeNode(RemovedQueueElement^.ItemName,Quantity);
            WriteLn;
            WriteLn(ClerkName,' has added ',RemovedQueueElement^.ItemQuantity,' more units of the item ',
                    RemovedQueueElement^.ItemName);
            WriteLn('to the store`s inventory.');
          End; { Else }
        Dispose(RemovedQueueElement);
      End; { While Not EmptyQueue }
  End;    { AddStockToItems }



  Procedure SellSomeItemStock;

  { This procedure processes the SellSomeItemStock queue.  This queue contains
    transactions to sell quantities of an item from the store's inventory.

    This procedure first assigns a mail order clerk to process the transaction.
    It then checks if the item exists in the store's inventory.  If item is not
    in the sore's inventory the transaction is left on the queue and the
    appropriate message is printed.  If there is not enough of the item in the
    store's inventory the transaction is again left on the queue and a message
    printed.  Otherwise the items are removed from the store's inventory and
    shipped, with the proper message given. }

  Var
    ClerkName:EntryString;               { name of the processing clerk }
    CurrentQueueElement:QueueElementPtr; { a pointer the current queue element being processed in the queue }
    RemovedQueueElement:QueueElementPtr; { a temporary pointer to the removed queue element }
    Quantity:Integer;                    { the number of items to be added to the store's inventory }
    ErrorCode:Integer;                   { an error code returned by the function Val }

  Begin   { SellSomeItemStock }
    CurrentQueueElement:=SellQuantityHeadPtr;
    While Not EmptyQueue(CurrentQueueElement) Do
      Begin
        DetermineMailOrderClerk(ClerkName);
        If Not ItemExist(CurrentQueueElement^.ItemName) Then
          Begin { item does not yet exist in store's inventory, postpone transaction until next day }
            WriteLn;
            WriteLn(ClerkName,' has found that ',CurrentQueueElement^.ItemName,' does not exist in the');
            WriteLn('in the store`s inventory to sell.  ',ClerkName,' has placed the');
            WriteLn('transaction back onto the queue for processing tomorrow.');
            CurrentQueueElement:=CurrentQueueElement^.Back; { increment queue element pointer }
          End { If Not ItemExist }
        Else
          Begin { item exists in store's inventory }
            Val(CurrentQueueElement^.ItemQuantity,Quantity,ErrorCode); { convert string quantity to an integer quantity }
            If Quantity>QuantityOfItem(CurrentQueueElement^.ItemName) Then
              Begin { insufficient stock of item, postpone transaction until next day }
                WriteLn;
                WriteLn(ClerkName,' has found insufficient inventory of the item ',
                        CurrentQueueElement^.ItemName);
                WriteLn('in the store`s inventory to sell.  ',ClerkName,' has placed the');
                WriteLn('transaction back onto the queue for processing tomorrow.');
                CurrentQueueElement:=CurrentQueueElement^.Back; { increment queue element pointer }
              End { If Quantity }
            Else
              Begin { sufficient stock of item, perform transaction }
                ReviseQuantityInTreeNode(CurrentQueueElement^.ItemName,-1*Quantity);
                WriteLn;
                WriteLn(ClerkName,' has sold ',CurrentQueueElement^.ItemQuantity,' units of the item ',
                        CurrentQueueElement^.ItemName);
                WriteLn('from the store`s inventory.');
                RemoveElementFromQueue(SellQuantityHeadPtr,SellQuantityTailPtr,CurrentQueueElement,RemovedQueueElement);
                Dispose(RemovedQueueElement);
              End; { Else }
          End; { Else }
      End; { While Not EmptyQueue }
  End;    { SellSomeItemStock }



  Procedure RemoveItemsFromInventory;

  { This procedure processes the RemoveItemFromInventory queue.  This queue
    contains transactions to delete items from the store's inventory.

    This procedure first assigns a mail order clerk to process the transaction.
    It then checks if the item already exists in the store's inventory.  If not
    then the appropriate error message is printed.  Otherwise the item is
    removed from the store's inventory with the appropriate message printed. }

  Var
    ClerkName:EntryString;             { name of the processing clerk }
    CurrentQueueElement:QueueElementPtr; { a pointer the current queue element being processed in the queue }
    RemovedQueueElement:QueueElementPtr; { a temporary pointer to the removed queue element }

  Begin   { RemoveItemsFromInventory }
    CurrentQueueElement:=RemoveItemHeadPtr;
    While Not EmptyQueue(CurrentQueueElement) Do
      Begin
        DetermineMailOrderClerk(ClerkName);
        RemoveElementFromQueue(RemoveItemHeadPtr,RemoveItemTailPtr,CurrentQueueElement,RemovedQueueElement);
        If Not ItemExist(RemovedQueueElement^.ItemName) Then
          Begin { item does not exist in store's inventory }
            WriteLn;
            WriteLn(ClerkName,' has found that ',RemovedQueueElement^.ItemName,' does not exist in the');
            WriteLn('store`s inventory and hence cannot be removed from the store`s inventory.');
          End { If Not ItemExist }
        Else
          Begin { remove item from store's inventory }
            DeleteElementFromTreeModule(RemovedQueueElement^.ItemName);
            WriteLn;
            WriteLn(ClerkName,' has removed the item ',RemovedQueueElement^.ItemName,' from the');
            WriteLn('store`s inventory.');
          End; { Else }
        Dispose(RemovedQueueElement);
      End; { While Not EmptyQueue }
  End;    { RemoveItemsFromInventory }



Begin   { ProcessDailyOrdersModule }
  PrintTransactionsHandledHeading;
  AddItemsToInventory;
  AddStockToItems;
  SellSomeItemStock;
  RemoveItemsFromInventory;
  PrintEmployeeQueue;
  PrintQueues;
End;    { ProcessDailyOrdersModule }



Procedure PrintDailyWorklogHeading(FileEntry:FileEntryString);

{ This procedure prints out the daily worklog heading for the daily worklog
  report. }

Var
  CurrentDay:EntryString;            { a string used to store the current day }

Begin   { PrintDailyWorklogHeading }
  CurrentDay:=ReturnThirdEntry(FileEntry);
  WriteLn;
  WriteLn;
  WriteLn('DAILY WORKLOG REPORT FOR DAY ',CurrentDay);
  WriteLn('------------------------------');
End;    { PrintDailyWorklogHeading }



Procedure ReadInputFile;

{ This procedure begins by first reading the entry in the declared file.  The
  file entry is in the form

             TransactionCode SecondEntry ThirdEntry

  The procedure then determines the transaction code that is contained in the
  file entry.  Possible transaction codes are:

              'N'    Insert a new item into the store's inventory
              'A'    Add a quantity to an existing item
              'S'    Sell a quantity of an existing item
              'R'    Remove an item from the store's inventory
              '*'    Add or delete a mail order clerk
              'X'    End of the business day, process orders

  This procedure then passes control to the specific procedure required.
  If none of the above transaction codes were entered in the file entry, the
  procedure prints an error message stating that a bad transaction code was
  entered. }

Var
  DataFile:Text;                       { Text File }
  FileEntry:FileEntryString;
  TransactionCodeEntry:FileEntryString;

Begin   { ReadInputFile }
  Assign(DataFile,FILE_NAME);          { assign to a disk file }
  Reset(DataFile);                     { open the file for reading }
  Repeat                               { read in the file entries }
    ReadLn(DataFile,FileEntry);
    TransactionCodeEntry:=TransactionCode(FileEntry);
    Case TransactionCodeEntry Of       { pass control to specific procedure }
      'N' : AddElementToQueue(NewItemHeadPtr,NewItemTailPtr,FileEntry);
      'A' : AddElementToQueue(AddQuantityHeadPtr,AddQuantityTailPtr,FileEntry);
      'S' : AddElementToQueue(SellQuantityHeadPtr,SellQuantityTailPtr,FileEntry);
      'R' : AddElementToQueue(RemoveItemHeadPtr,RemoveItemTailPtr,FileEntry);
      '*' : ProcessEmployeeModule(FileEntry);
      'X' : Begin
              PrintDailyWorklogHeading(FileEntry);
              ProcessDailyOrdersModule;
            End;
    Else                               { improper transaction code encountered }
(*    WriteLn;
      WriteLn('Bad transaction code was found in the following file entry:');
      WriteLn('   ',FileEntry); *)
    End; { Case TransactionCode(FileEntry) }
  Until Eof(DataFile);
  Close(DataFile);                     { close the disk file }
End;    { ReadInputFile }



Procedure PrintInventoryModule;

{ This module controls the printing out of the store's inventory in
  alphabetical order. }



  Procedure PrintInventoryHeading;

  { This procedure prints a heading identifying the store inventory list. }

  Begin   { PrintInventoryHeading }
    WriteLn;
    WriteLn;
    WriteLn;
    WriteLn('CURRENT MAIL ORDER STORE INVENTORY');
    WriteLn('----------------------------------');
    WriteLn;
    WriteLn('Quantity       Item');
  End;    { PrintInventoryHeading }



  Procedure InOrder(TreeNode:TreeNodePtr);

  { This recursive procedure is used to traverse a binary search tree and print
    out the node's ItemQuantity and ItemName in an inorder manner. }

  Begin   { InOrder }
    If TreeNode<>Nil Then
      Begin
        InOrder(TreeNode^.Left);         { make left branch recursive call }
        WriteLn;
        WriteLn('  ',TreeNode^.ItemQuantity,'       ',TreeNode^.ItemName);
        InOrder(TreeNode^.Right);       { make right branch recursive call }
      End; { If TreeNode }
  End;    { InOrder }



Begin   { PrintInventoryModule }
  PrintInventoryHeading;
  InOrder(TreeRootPtr);
End;    { PrintInventoryModule }



Procedure PrintBinaryTree;

{ This procedure prints out the binary search tree node data representing
  the tree structure it is stored in.  It calls a recursive inorder traversal
  procedure 'PrintNodesInorder' that travels down the right most subtree first.
  This recursive procedure does the actual printing of the binary search
  tree. }

Const
  Offset:Integer=15;                   { column offset used in the printing of each tree level }

Type
  ChildType=(Left,Right,Root);         { an enumerated data type used in helping to determine tree node child type }



  Procedure PrintNodesInorder(Node:TreeNodePtr;Level:Integer;Branch:ChildType);

  { This recursive procedure is used to print the nodes of a binary search
    tree.  It traverses the tree using an inorder traversal that goes to the
    right most subtree first. }

  Begin   { PrintNodesInorder }
    If Node=Nil Then                   { nil child node }
      If Node<>TreeRootPtr Then
        If Branch=Right Then
          WriteLn('/':Level*Offset,'Nil') { print right nil child node }
        Else
          WriteLn('\':Level*Offset,'Nil') { print left nil child node }
      Else
        WriteLn(' ':Level*Offset,'Nil') { print nil root }
    Else
      Begin
        PrintNodesInorder(Node^.Right,Level+1,Right); { traverse right subtree }
        If Node<>TreeRootPtr Then
          If Branch=Right Then
            WriteLn('/':Level*Offset,Node^.ItemName) { print right child node }
          Else
            WriteLn('\':Level*Offset,Node^.ItemName) { print left child node }
        Else
          WriteLn(' ':Level*Offset,Node^.ItemName); { print root }
        PrintNodesInorder(Node^.Left,Level+1,Left); { traverse left subtree }
      End; { Else }
  End;    { PrintNodesInorder }



Begin   { PrintBinaryTree }
  WriteLn;
  WriteLn;
  WriteLn('BINARY SEARCH TREE FOLLOWS:');
  WriteLn('---------------------------');
  WriteLn;
  WriteLn;
  PrintNodesInorder(TreeRootPtr,0,Root);
End;    { PrintBinaryTree }